package org.leetcode.medium;

import org.junit.Test;

/**
 * @author cheeho
 * Created on 2024/07/26
 */
public class LongestPalindrome {
    /**
     * 暴力搜索，做题超出时间限制
     *
     * @param s 字符串
     * @return 最长的回文子串
     */
    public String longestPalindrome(String s) {
        String maxPalindrome = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                StringBuilder sb = new StringBuilder();
                String str = s.substring(i, j + 1);
                sb.append(str);
                if (str.contentEquals(sb.reverse()) && maxPalindrome.length() < str.length()) {
                    maxPalindrome = str;
                }
            }
        }
        return maxPalindrome;
    }

    /**
     * 中心扩散算法，时间复杂度O(n^2) 拿空间换时间
     *
     * @param s 字符串
     * @return 最长的回文子串
     */
    public String longestPalindrome1(String s) {

        if (s == null || s.isEmpty()) {
            return "";
        }
        int strLen = s.length();
        int left;
        int right;
        int len = 1;
        int maxStart = 0;
        int maxLen = 0;

        for (int i = 0; i < strLen; i++) {
            left = i - 1;
            right = i + 1;
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                len++;
                left--;
            }
            while (right < strLen && s.charAt(right) == s.charAt(i)) {
                len++;
                right++;
            }
            while (left >= 0 && right < strLen && s.charAt(right) == s.charAt(left)) {
                len = len + 2;
                left--;
                right++;
            }
            if (len > maxLen) {
                maxLen = len;
                maxStart = left;
            }
            len = 1;
        }
        return s.substring(maxStart + 1, maxStart + maxLen + 1);

    }


    @Test
    public void test() {
        System.out.println(longestPalindrome1("aacabdkacaa"));
    }
}
